<!DOCTYPE html>
<html>
	<head>
		<meta charset="utf-8">
		<title>图结构</title>
	</head>
	<body>
	</body>
</html>
<script src="./dict.js" type="text/javascript" charset="utf-8"></script>
<script src="Queue.js" type="text/javascript" charset="utf-8"></script>
<script type="text/javascript">
	// 封装图结构
	/*
	图的遍历思想
		广度优先搜索（BFS）：基于队列，入队列的顶点先被搜索
		深度优先搜索（DFS）：基于栈或使用递归，经过将顶点存入栈中，顶点是沿着路径被探索，存在新的相邻
		顶点就去访问。
	使用三种颜色来反映状态：
		白色：表示该顶点还没有被访问
		灰色：表示该顶点被访问过，但并未被探索过
		黑色：表示该顶点被访问过且被完全探索过		
	广度优先算法的思路：
		广度优先算法会从指定的第一个顶点开始遍历图，先访问其所有的相邻点就像一次访问图的一层
		换句话说，就是先宽后深的访问顶点
	
	*/
	function Graph() {
		// 属性：顶点（数组），边（字典）
		this.vertexes = [] //顶点
		this.edges = new Dictionay() //边
		// 方法：
		// 添加方法：1。添加顶点，
		Graph.prototype.addVertexes = function(v) {
			this.vertexes.push(v)
			this.edges.set(v, [])
		}
		//2添加边
		Graph.prototype.addEdges = function(v1, v2) {
			this.edges.get(v1).push(v2)
			this.edges.get(v2).push(v1)
		}
		// 实现toString方法
		Graph.prototype.toString = function() {

			// 定义字符串，保存最终的结果
			var resultString = ''

			// 遍历所有的顶点,以及顶点对应的边
			for (var i = 0; i < this.vertexes.length; i++) {
				resultString += this.vertexes[i] + '->'
				var vEdges = this.edges.get(this.vertexes[i])

				for (var j = 0; j < vEdges.length; j++) {
					resultString += vEdges[j] + ' '
				}
				resultString += '\n'

			}

			return resultString
		}

		// 初始化状态颜色
		Graph.prototype.initialzeColr = function() {
			var colors = []
			for (var i = 0; i < this.vertexes.length; i++) {
				colors[this.vertexes[i]] = 'white'

			}
			return colors
		}
		// 广度优先搜索
		Graph.prototype.bfs = function(initV, handler) {
			// 1.初始化颜色
			var colors = this.initialzeColr()

			// 创建队列
			var queue = new Queue();

			// 将顶点加入到队列当中
			queue.enqueue(initV)
			// var v = queue.dequeue()
			// console.log('var v = queue.dequeue(',v)
			// 4.循环从队列中取出元素
			while (!queue.isEmpty()) {
				// 4.1. 从队列取出一个顶点
				var v = queue.dequeue()
				console.log('v',v)
				// 4.2 获取和顶点相连的另外顶点
				var vList = this.edges.get(v)
				// 4.3将v的颜色设置灰色
				colors[v] = 'gray'
				// 4.4遍历所有的顶点，并且加入到队列中
				for (var i = 0; i < vList.length; i++) {
					var e = vList[i]
					if (colors[e] == 'white') {
						colors[e] = 'gray'
						queue.enqueue(e)
					}
				}
				// 4.5 访问顶点
				handler(v)
				// 4.6将顶点设置为黑色
				colors[v] = 'black'
			}
		}
		// 深度优先搜索
		Graph.prototype.dfs = function(initv, handler) {
			// 1.初始化颜色
			var colors = this.initialzeColr()
			console.log('colors',colors)	
			// 2.从某个顶点开始递归访问
			this.dfsVisit(initv, colors, handler)
		}
		Graph.prototype.dfsVisit = function(v, colors, handler) {
			// 1.将颜色设置为灰色
			colors[v] = 'gray'

			// 2.处理v顶点
			handler(v)

			// 3.访问v相连的顶点
			var vList = this.edges.get(v)
			for (var i = 0; i < vList.length; i++) {
				var e = vList[i]
				if (colors[e] == 'white') {
					this.dfsVisit(e, colors, handler)
				}
			}
			// 4.将V设置为黑色
			colors[v] = 'black'
		}

	}

	// 测试代码
	// 1.创建图结构
	var graph = new Graph()
	// 添加顶点
	var myVertexes = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I']
	for (var i = 0; i < myVertexes.length; i++) {
		graph.addVertexes(myVertexes[i])
	}
	// 添加边
	graph.addEdges('A', 'B')
	graph.addEdges('A', 'C')
	graph.addEdges('A', 'D')
	graph.addEdges('C', 'D')
	graph.addEdges('C', 'G')
	graph.addEdges('D', 'G')
	graph.addEdges('D', 'H')
	graph.addEdges('B', 'E')
	graph.addEdges('B', 'F')
	graph.addEdges('E', 'I')

	// 
	// alert(graph)


	console.log('graph',graph)
	// 5.测试BFS
	var result = ''
	console.log('graph.vertexes[0]',graph.vertexes[0])
	graph.bfs(graph.vertexes[2], function(v) {
		result += v + ' '
	})
	console.log(result)
	// 测试DFS
	// var resultDfs = ''
	// graph.dfs(graph.vertexes[0], function(v) {
	// 	resultDfs += v + ' '
	// })
	// console.log('resultDfs', resultDfs)
</script>
